package 贪心;

import java.util.Arrays;
import java.util.PriorityQueue;
import org.junit.Test;

/**
 * 这个题 是经典的题
 * 无论从贪心的 角度 还是从 
 * 回溯 和  dp 该题都是一个好的题目   (区间  dp )
 * 首先这里复习一下堆的知识
 */
/**
 * 这个题 和   **石子合并**  有点相似 
 * 石子合并只能  dp （不能贪心）
 *  
 */
public class Zuo切木板OR石子合并 {

	
	public static void main(String []args) {
//		PriorityQueue<Integer> queue = new PriorityQueue<>();
//		queue.add(3);
//		queue.add(6);
//		queue.add(2);
//		queue.add(4);
//		System.out.println(queue);
//		for(int i : queue)
//			System.out.print(i + " ");
////		for(int i = 0; i < queue.size();i++)
////			System.out.println(queue.poll());
//		while(!queue.isEmpty()) {
//			System.out.println(queue.poll());
//		}
		int nums[] = {2,3,5,1,7};
		System.out.println(Arrays.toString(solution(nums)));
		
	}
	
	/**
	 * 先对 原数组  nums 进行 一个 copy 为了 让下标 从   1  开始
	 * 因为从  1  开始 的 时候  比较简单的 
	 */
	public static int[] solution(int nums[]) {
		int len = nums.length;
		int arr[] = new int [len + 1];
		int preSum [] = new int [len + 1];
		// 先构建 前缀和数组 (preSum)
		for(int i = 1;i <= len;i++) {
			arr[i] = nums[i - 1];
			preSum[i] = arr[i] + preSum[i - 1];
		}
		System.out.println(Arrays.toString(preSum));
		// 调用 process 函数
		return new int[] {dpOne(preSum),dp(preSum)};
//		return new int[] {};
	}
	
	
	// 区间 dp  关键的 core 在于 前缀数组的 引入(preSum 的引入 解决一个最大的问题)
	// 回溯
	public static int process(int i,int j,int []preSum) {
		if(i == j) 
			return 0;
		int ans = Integer.MAX_VALUE;
		for(int k = i;k < j;k++) {
			ans = Math.min(ans, process(i,k,preSum) + process(k + 1 ,j,preSum) + preSum[j] - preSum[i - 1]);
		}
		return ans;
		
	}
	
	// dp
	public static int dp(int []preSum) {
		int N = preSum.length;
		int dp[][] = new int[N][N];
		for(int i = N - 1;i >= 1;i--) {
			for(int j =  i;j < N;j++) {
				if(i == j)
					continue;
				int ans = Integer.MAX_VALUE;
				for(int k = i;k < j;k++) {
					ans = Math.min(ans, dp[i][k] + dp[k + 1][j] + preSum[j] - preSum[i - 1]);
				}
				dp[i][j] = ans; 
			}
		}
		for(int [] sub : dp)
			System.out.println(Arrays.toString(sub));
		return dp[1][N - 1];
	}
	
	
	public static int dpOne(int []preSum) {
		int N = preSum.length;
		int dp[][] = new int[N][N];
		for(int j = 1 ;j < N;j++) {
			for(int i = j; i >= 1;i--) {
				if(i == j)
					continue;
				int ans = Integer.MAX_VALUE;
				for(int k = i;k < j;k++) {
					ans = Math.min(ans, dp[i][k] + dp[k + 1][j] + preSum[j] - preSum[i - 1]);
				}
				dp[i][j] = ans; 
			}
		}
		for(int [] sub : dp)
			System.out.println(Arrays.toString(sub));
		return dp[1][N - 1];
	}
	
	/**
	 * 贪心的写法
	 * 使用堆
	 */
	public static int greedy(int nums[]) {
		int ans = 0;
		if(nums.length == 1)
			ans = nums[0];
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		for(int i = 0;i < nums.length; i++) {
			queue.add(nums[i]);
		}
		int temp = 0;
		while(queue.size() > 1) {
			temp = queue.poll() + queue.poll();
//			System.out.println(temp);
			ans += temp;
//			System.out.println(ans);
			queue.add(temp);
		}
		return ans;
	}
	
	
	
	@Test
	public void testRight() {
		int nums[] = {2,3,5,1,7};
		System.out.println(greedy(nums));
	}
	
	
}
